1. Field of the Invention
The present invention relates to information management systems and more particularly to an optimistic version number based concurrency control for memory-resident index structures.
2. Description of the Related Art
Database systems use indexes for efficient access to specific data items. Different tree structures, such as B-trees and tries (radix trees) are a method of choice for the indexes. In order to provide safe access by multiple processors at the same time, index trees employ a concurrency control method to protect different parts of the tree from being read or written by a processor while another processor is writing to the same place at the same time.
Concurrency control is important for multiprocessor scalability of an index structure. Typically, concurrency control entails the use of latches to lock a part of the index tree, usually a single node, against reading, writing, or both. The best scalability is attained by concurrency control methods that have a minimum amount of latch collisions, i.e., the same latch being wanted by two or more processors at the same time.
An optimistic, latch-free index traversal (“OLFIT”) scheme provides a method of protecting reads against simultaneous writes without latching a node. However, the OLFIT scheme only latches one node at a time when updating the tree, which means the OLFIT scheme must rely on the B-link method of node links when splitting nodes. This limits the applicability of the OLFIT scheme to B-link trees. Moreover, there is no method of joining two nodes. An index tree that requires latches on multiple levels for inserting or deleting a key can not benefit from the OLFIT scheme.
Therefore, there is a need for an optimistic latching method that can latch multiple levels of an index tree in database systems to allow the implementation of self-contained, one-go key insert and key delete.